package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 25. K 个一组翻转链表 困难题
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 *
 * @author zjj_admin
 * @date 2022/11/3 11:25
 */
public class ReverseNodesInKGroup {

    public static void main(String[] args) {

    }


    /**
     * 思路
     * 1、首先取得链表的总长度
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        //这只一个虚拟的头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        int length = 0;
        while (head != null){
            length ++;
            head = head.next;
        }
        head = dummy.next;
        ListNode pre = dummy;
        ListNode curr = head;
        ListNode next;
        for (int i = 0;i < length / k; i++){
            for (int j = 0; j < k - 1; j++) {
                //将这 k 个节点反转，逻辑 非常难 以 1 2 3 为例，初始 pre = 0，head = 1，curr = 1
                //每一次循环就是将后一个数据放在最前面
                //先将 curr 的下一个节点保存起来,，next = 2；
                next = curr.next;
                //将 curr 的 next 指向 3
                curr.next = next.next;
                //将 2 放在 0 的后面，及 1  的前面
                next.next = pre.next;
                //将 0的后面指向 2
                pre.next = next;
            }
            pre = curr;
            curr = pre.next;
        }
        return dummy.next;
    }

}
